package Tree;


import _4lists.src.queue.Tree;

import java.util.LinkedList;

/**
 * @className: Recursion_bianli
 * @description:
 * @author: myself
 * @date: 2025/7/27 19:35
 * @version: 0.1
 * @since: JDK17
 */
//递归实现二叉树的三种遍历
public class Recursion_bianli {
    //建立一个二叉树
    /*
    *                   1
    *             2           3
    *         4     null    5    6
    * */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6))
        );
        preOrder(root);
        /*System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);*/
    }

    //前序遍历
    /*前序遍历的特点
    * 1.先访问根节点
    * 2.然后返回左子树
    * 2.最后访问右子树
    * 访问结果：1，2，4，3，5，6*/
    static void preOrder(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur=root;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                System.out.println(cur.val);
                cur = cur.left;
            }else {
                TreeNode pop = stack.pop();
                System.out.println(pop.val);
                cur = pop.right;
            }
        }
    }

    //中续遍历
    /*中序遍历的特点
     * 1.先访问左子树
     * 2.然后返回根节点
     * 2.最后访问右子树
     * 访问结果：4，2，1，5，3，6*/
    static void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.val+"\t");
        inOrder(node.right);
    }

    //后续遍历
    /*前序遍历的特点
     * 1.先访问左子树
     * 2.然后返回右子树
     * 2.最后访问根节点
     * 访问结果：4，2，5，6，3，1*/
    static void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val+"\t");
    }
}
